/**
 * https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion/submissions/589892844/
 * 1186. 删除一次得到子数组最大和
 * medium 2024.12.28
 * 前缀和后缀和差分
 */

class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int n=arr.size();
        vector<int> leftmax(n);
        int pre=0;
        int ans=arr[0];
        for(int i=0;i<n;++i){
            pre=max(pre+arr[i],arr[i]);
            ans=max(ans,pre);
            leftmax[i]=pre;
        }
        pre=0;
        for(int i=n-1;i>1;--i){
            pre=max(pre+arr[i],arr[i]);
            ans=max(ans,pre+leftmax[i-2]);
        }
        return ans;
    }
};